Leetcode 44. Wildcard Matching 题解

题目链接

Leetcode 44. Wildcard Matching

题目内容

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example1:

Input: s = "aa" p = "a"

Output: false Explanation: "a" does not match the entire string "aa".

Example2:

Input: s = "aa" p = "*"

Output: true

Explanation: '*' matches any sequence.

解题思路

这题我一开始决定使用的是dp的方法进行解决，我们定义dp[i][j]为 p(0, i) 与 s(0, j)是否匹配，为了方便理解，我把规则字符串放到了前面

我们先看关于*以及s长度为0时的情况，若p字符前面的字符为'*'的话，我们就把到这个字符的dp[0][i]设置为true，之后就是false

正常情况

if p[j-1] != '*' dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == '?') && dp[i-1][j-1]

if p[j-1] == '*' dp[i][j] = dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];

但是时间复杂度不理想，所以寻找另一种更快的方案。

第二种方法则是直接顺着s字符串扫描下去，

while sindex < len(s):
    if p[pindex]== '?' or p[pindex] == s[sindex]:
        pindex++;
        sindex++;
        continue;
    else if p[pindex] == '*':
        # 记录星星位置以及sindex让pindex继续往后
        continue;
    if star != -1: 
        # 若星星后没有字符匹配的则让s从记录处继续往后扫，pindex也变为*位置+1, 直到扫描到一个匹配的字符或是sindex > s.size()为止

    # 若当前扫描到的位置没出现*，且字符没有匹配
    return false

若扫描完后, p字符串仍未扫完，看其后有无*, 继续扫描，结果判断pindex==p.size()。

这种方法复杂度比上面少了约一半，提交detail为

题目代码

一开始

class Solution {
    public:
    bool isMatch(string s, string p) {
        if(p.empty())
            return s.empty();
        int size1 = s.size(), size2 = p.size();
        bool dp[size1+1][size2+1];
        memset(dp,false,sizeof(dp));
        dp[0][0] = true;

        for(int i = 1; i <= size2; i++) {
            if(p[i-1] != '*')
                break;
            dp[0][i]=true;
        }

        for(int i=1; i<=size1; i++) {
            for(int j=1; j<=size2; j++) {
                bool f_match = s[i-1]==p[j-1] || p[j-1]=='?';
                if(p[j-1] == '*') {
                    dp[i][j] = dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];
                } else
                    dp[i][j] = f_match && dp[i-1][j-1];
            }
        }


        return dp[size1][size2];
    }
};

优化

class Solution {
    public:
    bool isMatch(string s, string p) {
        int star=-1;
        int ss;
        int pindex = 0,sindex=0;
        int size = s.size();
        while (sindex < size){
            if ((p[pindex]=='?') || (p[pindex]==s[sindex])){
                sindex++;
                pindex++;
                continue;
            } else if (p[pindex] == '*') {
                star=pindex++;
                ss=sindex;
                continue;
            }
            if (star!=-1) {
                pindex = star+1;
                sindex=++ss;
                continue;
            }
            return false;
        }
        while (p[pindex] == '*') {
            pindex++;
        }
        return pindex==p.size();
    }
};